home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / GNUST / !GNUst / st / Dictionary < prev    next >
Text File  |  1991-09-13  |  10KB  |  386 lines
  1. "======================================================================
  2. |
  3. |   Dictionary Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1990, 1991 Free Software Foundation, Inc.
  11. | Written by Steve Byrne.
  12. |
  13. | This file is part of GNU Smalltalk.
  14. |
  15. | GNU Smalltalk is free software; you can redistribute it and/or modify it
  16. | under the terms of the GNU General Public License as published by the Free
  17. | Software Foundation; either version 1, or (at your option) any later version.
  18. | 
  19. | GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20. | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21. | FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22. | details.
  23. | 
  24. | You should have received a copy of the GNU General Public License along with
  25. | GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26. | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27. |
  28.  ======================================================================"
  29.  
  30.  
  31. "
  32. |     Change Log
  33. | ============================================================================
  34. | Author       Date       Change 
  35. | sbb         12 Sep 91      Added Dictionary class>>new so subclasses can win.
  36. |
  37. | sbyrne      6 May 90      Fixed grow method to preserve associations in use in
  38. |              the dictionary instead of making new ones.  This
  39. |              should be faster, and doesn't break compiled methods
  40. |              that reference global variables when Smalltalk grows.
  41. |
  42. | sbyrne     24 Apr 90      Fix at:ifAbsent: to deal with failure better (and be
  43. |              a tad more efficient).  Kudos (or BarNone's,
  44. |              depending on preference) to Andy Valencia.
  45. |
  46. | sbyrne      7 Apr 90      Modified at:put: to resuse the existing Association
  47. |              if there is one, rather than create a new one all the
  48. |              time.  This was causing lossage when setting global
  49. |              variables in Smalltalk that previous usages weren't
  50. |              being changed.
  51. |
  52. | sbyrne     25 Apr 89      created.
  53. |
  54. "
  55.  
  56. Set variableSubclass: #Dictionary
  57.     instanceVariableNames: ''
  58.     classVariableNames: ''
  59.     poolDictionaries: ''
  60.     category: nil.
  61.  
  62. Dictionary comment: 
  63. 'I implement a dictionary, which is an object that is indexed by
  64. unique objects (typcially instances of Symbol), and associates another
  65. object with that index.  I use the equality operator = to determine
  66. equality of indices.' !
  67.  
  68. "### The initblocks variable should not be globally visible, I think"
  69. "This is a HACK HACK HACK.  We want to reference the InitBlocks global variable
  70. from within some methods in System Dictionary.  However, after this file
  71. redefines at:put: from the built-in one, and until UndefinedObject.st is 
  72. loaded, defining isNil for nil, at:put: for dictionaries does not work
  73. properly.  So we do it here.  The basic problem is that InitBlocks should
  74. maybe be kept elsewhere, and not be globally visible."
  75. Smalltalk at: #InitBlocks put: nil!
  76.  
  77. !Dictionary class methodsFor: 'instance creation'!
  78.  
  79. new
  80.     "Builtins defines a #new method, so that during bootstrap there is a way
  81.      to create dictionaries.  Unfortunately, this #new method only creates
  82.      dictionaries, so subclasses when trying to use this method, lose big.
  83.      This fixes the problem."
  84.     ^self new: 32
  85. ! !
  86.  
  87.  
  88. !Dictionary methodsFor: 'accessing'!
  89. add: anAssociation
  90.     | index |
  91.     index _ self findKeyIndex: anAssociation key.
  92.     (self basicAt: index) isNil
  93.     ifTrue: [ tally _ tally + 1].
  94.     self basicAt: index put: anAssociation.
  95.     ^anAssociation
  96. !
  97.  
  98. at: key put: value
  99.     | index assoc |
  100.     index _ self findKeyIndex: key.
  101.     (assoc _ self basicAt: index) isNil
  102.     ifTrue: [ self basicAt: index
  103.                put: (Association key: key value: value).
  104.           tally _ tally + 1 ]
  105.     ifFalse: [ assoc value: value ].
  106.     ^value
  107. !
  108.  
  109. at: key
  110.     ^self at: key ifAbsent: [ ^self error: 'key not found' ]
  111. !
  112.  
  113. at: key ifAbsent: aBlock
  114.     | assoc |
  115.     assoc _ self basicAt: (self findKeyIndex: key).
  116.     assoc isNil
  117.             ifTrue: [ ^aBlock value ]
  118.             ifFalse: [ ^assoc value ]
  119. !
  120.     
  121. associationAt: key
  122.     ^self associationAt: key ifAbsent: [ ^self error: 'key not found' ]
  123. !
  124.  
  125. associationAt: key ifAbsent: aBlock
  126.     | index assoc|
  127.     index _ self findKeyIndex: key.
  128.     assoc _ self basicAt: index.
  129.     assoc isNil ifTrue: [ ^aBlock value ]
  130.                 ifFalse: [ ^assoc ]
  131. !
  132.  
  133. keyAtValue: value ifAbsent: exceptionBlock
  134.     self associationsDo:
  135.         [ :assoc | value = assoc value
  136.                  ifTrue: [ ^assoc key ] ].
  137.     ^exceptionBlock value
  138. !
  139.  
  140. keyAtValue: value
  141.     ^self keyAtValue: value ifAbsent: []
  142. !
  143.  
  144. keys
  145.     | aSet |
  146.     aSet _ Set new: tally.
  147.     self keysDo: [ :aKey | aSet add: aKey ].
  148.     ^aSet
  149. !
  150.  
  151. values
  152.     | aBag |
  153.     aBag _ Bag new.
  154.     self do: [ :aValue | aBag add: aValue ].
  155.     ^aBag
  156. !!
  157.  
  158.  
  159.  
  160. !Dictionary methodsFor: 'dictionary testing'!
  161.  
  162. includesAssociation: anAssociation
  163.     | assoc |
  164.     assoc _ self associationAt: anAssociation key ifAbsent: [ ^false ].
  165.     ^assoc value = anAssociation value
  166. !
  167.  
  168. includesKey: key
  169.     self associationAt: key ifAbsent: [ ^false ].
  170.     ^true
  171. !
  172.  
  173. includes: anObject
  174.     self do: [ :element | element = anObject ifTrue: [ ^true ] ].
  175.     ^false
  176. !
  177.  
  178. occurrencesOf: aValue
  179.     | count |
  180.     count _ 0.
  181.     self do: [ :element | element = aValue
  182.                     ifTrue: [ count _ count + 1] ].
  183.     ^count
  184. !!
  185.  
  186.  
  187.  
  188. !Dictionary methodsFor: 'dictionary removing'!
  189.  
  190. removeAssociation: anAssociation
  191.     "### does this check the value as well as the key?"
  192.     self removeKey: anAssociation key ifAbsent: [].
  193.     ^anAssociation
  194. !
  195.  
  196. removeKey: key
  197.     ^self removeKey: key ifAbsent: [ ^self error: 'key not found' ]
  198. !
  199.  
  200. removeKey: key ifAbsent: aBlock
  201.     | index assoc |
  202.     index _ self findKeyIndexNoGrow: key ifAbsent: [ ^aBlock value ].
  203.     assoc _ self basicAt: index.
  204.     self basicAt: index put: nil.
  205.     tally _ tally - 1.
  206.     self rehashObjectsAfter: index.
  207.     ^assoc value
  208. !
  209.  
  210. remove: anObject
  211.     self error: 'remove: not allowed in Dictionary'
  212. !
  213.  
  214. remove: anObject ifAbsent: aBlock
  215.     self error: 'remove:ifAbsent: not allowed in Dictionary'
  216. !!
  217.  
  218.  
  219.  
  220. !Dictionary methodsFor: 'dictionary enumerating'!
  221. associationsDo: aBlock
  222.     super do: [ :assoc | aBlock value: assoc ]
  223. !
  224.  
  225. "These could be implemented more efficiently by doing the super do
  226.  directly, or doing the explicit scanning of the dictionary by hand"
  227. keysDo: aBlock
  228.     self associationsDo: [ :assoc | aBlock value: assoc key ]
  229. !
  230.  
  231. do: aBlock
  232.     self associationsDo: [ :assoc | aBlock value: assoc value ]
  233. !
  234.  
  235. collect: aBlock
  236.     | aBag |
  237.     aBag _ Bag new.
  238.     self do: [ :element | aBag add: (aBlock value: element) ].
  239.     ^aBag
  240. !
  241.  
  242. select: aBlock
  243.     | newDict |
  244.     newDict _ self species new.
  245.     self associationsDo:
  246.         [ :assoc | (aBlock value: assoc value)
  247.              ifTrue: [ newDict add: assoc ] ].
  248.     ^newDict
  249. !
  250.  
  251. reject: aBlock
  252.     self shouldNotImplement
  253. !
  254.  
  255. inject: value into: aBlock
  256.     self shouldNotImplement
  257. !!
  258.  
  259.  
  260.  
  261. !Dictionary methodsFor: 'misc math methods'!
  262.  
  263. = aDictionary
  264.     tally ~= aDictionary size ifTrue: [ ^false ].
  265.     self associationsDo:
  266.         [ :assoc | assoc value ~= (aDictionary at: assoc key
  267.                                            ifAbsent: [ ^false ])
  268.                      ifTrue: [ ^false ] ].
  269.     ^true
  270. !
  271.  
  272. hash
  273.     | hashValue |
  274.     hashValue _ tally.
  275.     self associationsDo:
  276.         [ :assoc | hashValue _ hashValue + assoc hash ].
  277.     ^hashValue
  278. !!
  279.  
  280.  
  281.  
  282. !Dictionary methodsFor: 'printing'!
  283.  
  284. printOn: aStream
  285.     aStream nextPutAll: self class name , ' (' .
  286.     self associationsDo:
  287.         [ :assoc | assoc key storeOn: aStream.
  288.                aStream nextPut: $,.
  289.            assoc value storeOn: aStream.
  290.            aStream nextPut: Character space ].
  291.     aStream nextPut: $)
  292. !!
  293.  
  294.  
  295.  
  296. !Dictionary methodsFor: 'storing'!
  297.  
  298. storeOn: aStream
  299.     | hasElements |
  300.     aStream nextPutAll: '(', self class name , ' new'.
  301.     hasElements _ false.
  302.     self associationsDo:
  303.         [ :assoc | aStream nextPutAll: ' at: '.
  304.                    assoc key storeOn: aStream.
  305.                aStream nextPutAll: ' put: '.
  306.            assoc value storeOn: aStream.
  307.            aStream nextPut: $;.
  308.            hasElements _ true ].
  309.     hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
  310.     aStream nextPut: $)
  311. !!
  312.  
  313.  
  314.  
  315. !Dictionary methodsFor: 'private methods'!
  316.  
  317. rehashObjectsAfter: index
  318.     "Rehashes all the objects in the collection after index to see if any of
  319.     them hash to index.  If so, that object is copied to index, and the
  320.     process repeats with that object's index, until a nil is encountered."
  321.     | i size count assoc |
  322.     i _ index.
  323.     size _ self basicSize.
  324.     count _ size.
  325.     [ count > 0 ]
  326.         whileTrue:
  327.         [ i _ i \\ size + 1.
  328.               assoc _ self basicAt: i.
  329.           assoc isNil ifTrue: [ ^self ].
  330.               ((assoc key hash \\ size) + 1) = index
  331.               ifTrue: [ self basicAt: index put: assoc.
  332.                   self basicAt: i put: nil.  "Be tidy"
  333.               index _ i ].
  334.               count _ count - 1 ]
  335. !
  336.  
  337. findKeyIndex: aKey ifFull: aBlock
  338.     "Tries to see if aKey exists as the key of an indexed variable (which is an
  339.     association).  If it's searched the entire dictionary and the key is 
  340.     not to be found, aBlock is evaluated and it's value is returned."
  341.     | index count size assoc |
  342.     size _ self basicSize.
  343.     index _ aKey hash \\ size + 1.
  344.     count _ size.
  345.     [ count > 0 ]
  346.         whileTrue:
  347.         [ assoc _ self basicAt: index.
  348.               (assoc isNil or: [ assoc key = aKey ])
  349.             ifTrue: [ ^index ].
  350.           index _ index \\ size + 1.
  351.           count _ count - 1. ].
  352.     ^aBlock value
  353. !
  354.         
  355. findKeyIndex: aKey
  356.     "Finds an association with the given key in the dictionary and returns its
  357.     index.  If the dictionary doesn't contain the object and there is no nil
  358.     element, the dictionary is grown and then the index of where the object
  359.     would go is returned."
  360.     ^self findKeyIndex: aKey
  361.            ifFull: [ self grow.
  362.                 self findKeyIndexNoGrow: aKey
  363.                   ifAbsent: [ ^self error: 'failed to grow a new empty element!!!' ] ]
  364. !
  365.  
  366. findKeyIndexNoGrow: aKey ifAbsent: aBlock
  367.     | index |
  368.     index _ self findKeyIndex: aKey ifFull: [ 0 ].
  369.     (index = 0 )
  370.         ifTrue: [ ^aBlock value ]
  371.     ifFalse: [ ^index ]
  372. !
  373.  
  374. grow
  375.     | newDict |
  376.     newDict _ self species new: self basicSize + self growSize.
  377.     self associationsDo: [ :assoc | newDict add: assoc ].
  378.     ^self become: newDict
  379. !
  380.  
  381. growSize
  382.     ^32
  383.  
  384. !!
  385.  
  386.